import random


class AiBrain:
    def __init__(self):
        self.scores = {
            "ai": 10,
            "man": -10,
            "tie": 0
        }
        self.man = 1
        self.ai = 2

    def next(self, board):
        # return self.random_next(board)
        # return self.clever_next(board)
        return self.smart_next(board)

    # 随机策略，很傻很天真
    def random_next(self, board):
        spaces = self.find_empty_tiles(board)

        if len(spaces) > 0:
            return random.choice(spaces)
        else:
            return None, None

    # 自定义规则
    """
    2.1 自己或对方是否有“二连”，如果有，则在“三连”位置下子或堵截； 
    2.2 边角是否有空，有则随即选择 
    2.3 中间位（2，2）是否空，如空，则选择 
    2.4 四边空位随机选择
    """
    def clever_next(self, board):
        if self.has_winner(board):
            return None
        elif self.is_board_full(board):
            return None

        spaces = self.find_empty_tiles(board)
        for pos in spaces:
            ri, ci = pos

            board[ri][ci] = self.ai
            if self.has_winner(board):
                board[ri][ci] = 0
                return ri, ci
            board[ri][ci] = 0

            board[ri][ci] = self.man
            if self.has_winner(board):
                board[ri][ci] = 0
                return ri, ci
            board[ri][ci] = 0

        corner_spaces = []
        if board[0][0] == 0: corner_spaces.append((0, 0))
        if board[0][2] == 0: corner_spaces.append((0, 2))
        if board[2][0] == 0: corner_spaces.append((2, 0))
        if board[2][2] == 0: corner_spaces.append((2, 2))
        if len(corner_spaces) > 0:
            return(random.choice(corner_spaces))

        if board[1][1] == 0:
            return 1,1

        edge_spaces = []
        if board[0][1] == 0: edge_spaces.append((0, 1))
        if board[1][0] == 0: edge_spaces.append((1, 0))
        if board[1][2] == 0: edge_spaces.append((1, 2))
        if board[2][1] == 0: edge_spaces.append((2, 1))
        return(random.choice(edge_spaces))


    # minimax brain 极小极大树搜索
    def smart_next(self, board):

        best_score = -float('inf')
        best_pos = (None, None)
        spaces = self.find_empty_tiles(board)
        if len(spaces) > 0:
            for pos in spaces:
                board[pos[0]][pos[1]] = 2
                s = self.minimax(board, 0, "man")
                if s > best_score:
                    best_score = s
                    best_pos = pos
                board[pos[0]][pos[1]] = 0
            return best_pos


    def has_winner(self, board):
        # check row
        if board[0][0] == board[0][1] == board[0][2] and board[0][0] != 0:
            return board[0][0]
        if board[1][0] == board[1][1] == board[1][2] and board[1][0] != 0:
            return board[1][0]
        if board[2][0] == board[2][1] == board[2][2] and board[2][0] != 0:
            return board[2][0]
        # check column
        if board[0][0] == board[1][0] == board[2][0] and board[0][0] != 0:
            return board[0][0]
        if board[0][1] == board[1][1] == board[2][1] and board[0][1] != 0:
            return board[0][1]
        if board[0][2] == board[1][2] == board[2][2] and board[0][2] != 0:
            return board[0][2]
        # check X lines
        if board[0][0] == board[1][1] == board[2][2] and board[0][0] != 0:
            return board[0][0]
        if board[0][2] == board[1][1] == board[2][0] and board[0][2] != 0:
            return board[0][2]
        # else
        return None


    def find_empty_tiles(self, board):
        spaces = []
        for ri, row in enumerate(board):
            for ci, col in enumerate(row):
                if col == 0:
                    spaces.append((ri, ci))
        return spaces

    def is_board_full(self, board):
        for row in board:
            for col in row:
                if col == 0:
                    return False
        return True

    def minimax(self, board, depth, turn):
        w = self.has_winner(board)
        if w == self.man:
            return self.scores["man"]
        elif w == self.ai:
            return self.scores["ai"]

        if self.is_board_full(board):
            return self.scores["tie"]

        # ai
        if turn == "ai":
            best_score = -float('inf')
            spaces = self.find_empty_tiles(board)
            for pos in spaces:
                board[pos[0]][pos[1]] = self.ai
                score = self.minimax(board, 0, "man")
                board[pos[0]][pos[1]] = 0
                if score > best_score:
                    best_score = score
            return best_score

        # man
        if turn == "man":
            best_score = float('inf')
            spaces = self.find_empty_tiles(board)
            for pos in spaces:
                row, col = pos
                board[row][col] = self.man
                score = self.minimax(board, 0, "ai")
                board[row][col] = 0
                if score < best_score:
                    best_score = score
            return best_score

